/*
    created: 2023/4/17
    filename: KMP.c
    author： 李东霖
    purpose: KMP算法的实现  

*/

#include"KMP.h"


void GetNext(const char* str,int next[])
{
    if(str == NULL || next == NULL) return;
    int slen = strlen(str);

    //如果模式串的长度小于3 NULL -1 0 
    if(slen == 0) return;
    if(slen == 1) {next[0] = -1;return;}
    if(slen == 2) {next[0] = -1,next[1] = 0; return;}

    next[0] = -1;
    next[1] = 0;

    //开始取前后缀 
    for(int i = 2;i != slen;++i)
    {
        //表示最长公共前后缀长度  
        int maxlen = 0;
        for(int j = 1;j != i;++j)
        {
            char p1[slen],p2[slen];
            memset(p1,0,sizeof(p1));
            memset(p2,0,sizeof(p2));
            //取前缀
            strncpy(p1,str,j); 
            //取后缀
            strncpy(p2,str+i-j,j);
            if(strcmp(p1,p2)==0) maxlen = j;
        }
        next[i] = maxlen;
    }
    return ;
}

void GetNextval(const char* str,int next[],int nextval[])
{
    if(str == NULL || next == NULL || nextval == NULL) return;
    int len = strlen(str);
    nextval[0] = -1;
    for(int i = 1; i != len;++i)
    {
        if(str[i]==str[next[i]])
        {
            nextval[i] = nextval[next[i]];
        }
        else 
        {
            nextval[i] = next[i];
        }
    }
}


int Index_Kmp(char sstr[],char dstr[])
{
    int next[strlen(dstr)];
    int nextval[strlen(dstr)];
    memset(next,0,sizeof(next));
    memset(nextval,0,sizeof(nextval));
    GetNext(sstr,next);
    GetNextval(sstr,next,nextval);
    int i = 0;
    int j = 0;
    int sstrlen = strlen(sstr);
    int dstrlen = strlen(dstr);
    while(i != sstrlen && j != dstrlen)
    {
        if(j == -1 || sstr[i] == dstr[j])
        {
            ++i,++j;
        } 
        else
        {
            //next数组回溯
            // j = next[j]; 
            j = nextval[j]; 
        }

    }
    if(j = dstrlen) return i-dstrlen;
}